package sort;

import java.util.Arrays;

/**
 * 描述:
 *  1.最优时间复杂度：nlogn，最差时间复杂度：n2，平均时间复杂度nlogn
 *  2.最优空间复杂度：logn，最差n
 *
 * @author
 * @created 2021/12/30 9:04
 */
public class FastSort {

    public static void main(String[] args) {
        int[] arr = new int[]{5, 6, 67, 7, 87, 4, 3, 23, 45, 6, 7, 78, 6, 4, 43, 5, 6, 67, 67};
        fastSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void fastSort(int[] arr) {
        fastSort(arr, 0, arr.length - 1);
    }

    public static void fastSort(int[] arr, int left, int right) {
        if (left <= right) {
            int base = arr[left];
            int i = left;
            int j = right;
            while (i != j) {
                while (arr[j] >= base && i < j) {
                    j--;
                }
                while (arr[i] <= base && i < j) {
                    i++;
                }
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
            arr[left] = arr[i];
            arr[i] = base;
            fastSort(arr, 0, i - 1);
            fastSort(arr, j + 1, right);
        }
    }

}
